package me.eg.fifth;

import java.util.HashMap;
import java.util.Map;

/**
 * 911. 在线选举
 * <p>
 * 在选举中，第 i 张票是在时间为 times[i] 时投给 persons[i] 的。
 * <p>
 * 现在，我们想要实现下面的查询函数： TopVotedCandidate.q(int t) 将返回在 t 时刻主导选举的候选人的编号。
 * <p>
 * 在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。
 * <p>
 * 示例：
 * 输入：["TopVotedCandidate","q","q","q","q","q","q"], [[[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]],[3],[12],[25],[15],[24],[8]]
 * 输出：[null,0,1,1,0,0,1]
 * 解释：
 * 时间为 3，票数分布情况是 [0]，编号为 0 的候选人领先。
 * 时间为 12，票数分布情况是 [0,1,1]，编号为 1 的候选人领先。
 * 时间为 25，票数分布情况是 [0,1,1,0,0,1]，编号为 1 的候选人领先（因为最近的投票结果是平局）。
 * 在时间 15、24 和 8 处继续执行 3 个查询。
 * <p>
 * 链接：https://leetcode-cn.com/problems/online-election
 */
public class TopVotedCandidate {
    private int[] times;
    private int[] votesCandidate;
    private int n;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.n = persons.length;
        this.times = times;
        this.votesCandidate = new int[n];
        Map<Integer, Integer> votes = new HashMap<>();
        votesCandidate[0] = persons[0];
        votes.put(persons[0], 1);
        for (int i = 1; i < n; i++) {
            int tVotes = votes.getOrDefault(persons[i], 0) + 1;
            votes.put(persons[i], tVotes);
            if (tVotes >= votes.get(votesCandidate[i - 1])) {
                votesCandidate[i] = persons[i];
            } else {
                votesCandidate[i] = votesCandidate[i - 1];
            }
        }
    }

    public int q(int t) {
        /**
         * 解法一：找小于等于 t 的最大值
         */
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (times[mid] <= t) left = mid;
            else right = mid - 1;
        }
        return votesCandidate[right];

        /**
         * 解法二：找大于等于 t 的最小值
         */
//        int left = 0, right = n;
//        while (left < right) {
//            int mid = (left + right) >> 1;
//            if (times[mid] >= t) right = mid;
//            else left = mid + 1;
//        }
//        return right == n || times[right] > t ? votesCandidate[right - 1] : votesCandidate[right];
    }
}
